#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>
#include <stack>
#include <queue>


class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> ret(m, vector<int>(n));
        ret[0][0] = 1;
        for (int x = 0; x < m; x++)
        {
            for (int y = 0; y < n; y++)
            {
                if (x - 1 >= 0)
                {
                    ret[x][y] += ret[x - 1][y];
                }
                if (y - 1 >= 0)
                {
                    ret[x][y] += ret[x][y - 1];
                }
            }
        }
        return ret[m - 1][n - 1];
    }
};

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        int m = obstacleGrid[0].size();
        vector<vector<int>> ret(n, vector<int>(m));
        ret[0][0] = 1;
        for (int x = 0; x < n; x++)
        {
            for (int y = 0; y < m; y++)
            {
                if (obstacleGrid[x][y] == 1)
                {
                    ret[x][y] = 0;
                    continue;
                }
                if (x - 1 >= 0)
                {
                    ret[x][y] += ret[x - 1][y];
                }
                if (y - 1 >= 0)
                {
                    ret[x][y] += ret[x][y - 1];
                }
            }
        }
        return ret[n - 1][m - 1];
    }
};

class Solution {
public:
    void Adject(vector<int>& gifts, int n, int p)
    {
        int parent = p;
        int child = parent * 2 + 1;
        while (child < n)
        {
            if (child + 1 < n && gifts[child + 1] > gifts[child])
            {
                child++;
            }
            if (gifts[child] > gifts[parent])
            {
                swap(gifts[child], gifts[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    long long pickGifts(vector<int>& gifts, int k) {
        int n = gifts.size();
        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
        {
            Adject(gifts, n, i);
        }
        while (k--)
        {
            gifts[0] = sqrt(gifts[0]);
            Adject(gifts, n, 0);
        }
        long long ret = 0;
        for (int i = 0; i < n; i++)
        {
            ret += gifts[i];
        }
        return ret;
    }
};

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>> ret(m + 1, vector<int>(n + 1));
        for (int x = 1; x <= m; x++)
        {
            for (int y = 1; y <= n; y++)
            {
                ret[x][y] = max(ret[x - 1][y], ret[x][y - 1]) + frame[x - 1][y - 1];
            }
        }
        return ret[m][n];
    }
};

class Solution {
public:
    int minAddToMakeValid(string s) {
        int ret = 0;
        stack<char> st;
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '(')
            {
                st.push(s[i]);
            }
            else if (s[i] == ')' && !st.empty())
            {
                st.pop();
            }
            else
            {
                ret++;
            }
        }
        while (!st.empty())
        {
            st.pop();
            ret++;
        }
        return ret;
    }
};



struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr)
        {
            return ret;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty())
        {
            int len = q.size();
            int my_max = INT_MIN;
            while (len--)
            {
                TreeNode* node = q.front();
                q.pop();
                TreeNode* left = node->left;
                if (left)
                {
                    q.push(left);
                }
                TreeNode* right = node->right;
                if (right)
                {
                    q.push(right);
                }
                if (node->val > my_max)
                {
                    my_max = node->val;
                }
            }
            ret.push_back(my_max);
        }
        return ret;
    }
};

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> ret(n + 1, vector<int>(n + 2, INT_MAX));
        for (int i = 0; i < n + 2; i++)
        {
            ret[0][i] = 0;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                ret[i][j] = min(ret[i - 1][j], min(ret[i - 1][j - 1], ret[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        int my_min = INT_MAX;
        for (int i = 1; i <= n; i++)
        {
            if (my_min > ret[n][i])
            {
                my_min = ret[n][i];
            }
        }
        return my_min;
    }
};